package linear

import (
    "fmt"
    "reflect"
    "strings"
)

type node struct {
    data interface{}
    next *node
}

// LinkList 单向链表
type LinkList struct {
    head *node
    len  int
}

func NewLinkList() *LinkList {
    head := &node{
        data: nil,
        next: nil,
    }
    return &LinkList{
        head: head,
        len:  0,
    }
}

func (l *LinkList) Length() int {
    return l.len
}

func (l *LinkList) isEmpty() bool {
    return l.len == 0
}

func (l *LinkList) Get(index int) *node {
    node := l.head
    for i := 0; i < index; i++ {
        node = node.next
    }
    return node
}

func (l *LinkList) Insert(data interface{}) {
    lastNode := l.Get(l.len)
    newNode := &node{
        data: data,
        next: nil,
    }
    lastNode.next = newNode
    l.len++
}

func (l *LinkList) InsertI(index int, data interface{}) {
    preNode := l.Get(index - 1)
    curNode := preNode.next
    newNode := &node{
        data: data,
        next: curNode,
    }
    preNode.next = newNode
    l.len++
}

func (l *LinkList) Remove(index int) *node {
    preNode := l.Get(index - 1)
    curNode := preNode.next
    nextNode := curNode.next
    preNode.next = nextNode
    l.len--
    return curNode
}

func (l *LinkList) Clear() {
    l.head.next = nil
    l.len = 0
}

func (l *LinkList) IndexOf(data interface{}) int {
    node := l.head
    for i := 0; i <= l.len; i++ {
        if reflect.DeepEqual(node.data, data) {
            return i
        }
        node = node.next
    }
    return -1
}

func (l *LinkList) Reverse() *node {
    if l.len <= 1 {
        return l.head.next
    }

    return l.ReverseI(l.head.next)
}

func (l *LinkList) ReverseI(current *node) *node {
    if current.next == nil {
        l.head.next = current
        return current
    }

    pre := l.ReverseI(current.next)
    pre.next = current
    current.next = nil
    return current
}

func (l *LinkList) Print() {
    node := l.head
    str := "["
    for i := 0; i < l.len; i++ {
        node = node.next
        str += fmt.Sprintf("%v ", node)
    }
    str = strings.TrimSuffix(str, " ")
    str += "]"
    fmt.Println(str)
}
